package airthmetic.exercise.dp;

public class _416_分割等和子集 {

    // 普通动态规划
    public static boolean canPartition(int[] nums) {
        // 转换成0-1背包问题
        int N = nums.length;
        // 剪枝1 如果数组元素之和最终不是偶数，肯定不存在分割等和子集
        int count = 0;
        int max = 0;
        for(int num : nums){
            max = Math.max(max, num);
            count+=num;
        }
        if(count % 2 != 0){
            return false;
        }
        // 剪枝2 如果数组中最大的元素大于数组元素之和的一半，则肯定不存在分割等和子集
        int W = count >> 1;
        if(max > W){
            return false;
        }

        boolean[][] dp = new boolean[N+1][W+1];
        for(int j=0; j<W+1; j++){
            dp[0][j] = false;
        }
        for(int i=0; i<N+1; i++){
            dp[i][0] = true;
        }


        for(int i=1; i<N+1; i++){
            for(int w=1; w<W+1; w++){
                if(nums[i-1] > w){
                    dp[i][w] = dp[i-1][w];
                }else{
                    dp[i][w] = dp[i-1][w] || dp[i-1][w-nums[i-1]];
                }
            }
        }

        return dp[N][W];

    }

    // 状态压缩动态规划
    // 根据结果我们发现求解问题dp[i][w]只需要用到dp[i-1][w] 或dp[i-1][w-nums[i-1]]  所以我们只用上一行或者上一行的钱前几个结果。
    // 那么可以把dp table 压缩成一维
    // 但是需要注意我们不能再0~w遍历了。
    // 举例：从0~w遍历当我们求解dp[2]时会用到要用到dp[1]或者dp[0]。当我们用完,需要更新dp[2]。再求解dp[3]的时候如果用到dp[2]已经不能再使用dp[2]，因为dp[2]是当前层的解
    // 所以我们从w~0遍历完美解决上述问题
    public static boolean canPartition2(int[] nums) {
        // 转换成0-1背包问题
        int N = nums.length;
        // 剪枝1 如果数组元素之和最终不是偶数，肯定不存在分割等和子集
        int count = 0;
        int max = 0;
        for(int num : nums){
            max = Math.max(max, num);
            count+=num;
        }
        if(count % 2 != 0){
            return false;
        }
        // 剪枝2 如果数组中最大的元素大于数组元素之和的一半，则肯定不存在分割等和子集
        int W = count >> 1;
        if(max > W){
            return false;
        }

        boolean[] dp = new boolean[W+1];
        dp[0] = true;

        for(int i=1; i<N+1; i++){
            for(int w=W; w>=0; w--){
//                if(nums[i-1] > w){
//                    dp[w] = dp[w];
//                }else{
//                    dp[w] = dp[w] || dp[w-nums[i-1]];
//                }

                if(nums[i-1] <= w){
                    dp[w] = dp[w] || dp[w-nums[i-1]];
                }
            }
        }

        return dp[W];

    }


    // 状态压缩
    public boolean canPartition3(int[] nums) {
        /**
         因为问题具备重叠子问题和无后效性及最优子结构。 动态规划！
         想办法把他变成0-1背包问题。
         动态规划思考问题：
         什么是原问题？ 什么是子问题？
         原问题：nums的所有元素，凑成nums元素之和的一半
         子问题：nums的前N个元素凑成nums元素之和的一半

         1.确认状态参数和选择
         状态参数：背包重量 nums元素之和的一半
         物品数量 nums.length

         选择/决策：不断选择物品数量和背包重量

         2.定义 dp table的含义
         boolean[][] dp = new boolean[nums.length][nums元素之和的一半];
         dp[i][w]表示 前i个物品 在w背包容量下能否装满

         3.初始化 dp table
         当物品为0的时候 无论背包容量有多少都不能装满
         当背包容量为0的时候 无论物品数量是多少个都可以装满背包（不装物品）

         4.推导状态转移公式
         for(int i=1; i<=nums.length; i++){
         for(int w=1; w<=amount; w++){
         if(nums[i-1] > w){
         dp[i][w] = dp[i-1][w];
         }else{
         dp[i][w] = dp[i-1][w] || dp[i - 1][w - nums[i-1]];
         }
         }
         }
         */

        int amount = 0;
        int max = 0;
        for(int i=0; i<nums.length; i++){
            amount += nums[i];
            max = Math.max(nums[i], max);
        }

        if(amount % 2 != 0){
            return false;
        }
        int W = amount / 2;
        if(max > W){
            return false;
        }
        int N = nums.length;
        boolean[] dp = new boolean[W+1];
        dp[0] = true;

        for(int i=1; i<=N; i++){
            for(int w=W; w>=0; w--){
                if(nums[i-1] <= w){
                    dp[w] = dp[w] || dp[w - nums[i-1]];
                }
            }
        }
        return dp[W];
    }


    public static void main(String[] args) {
        int[] nums = new int[]{1,5,11,5};

        System.out.println(canPartition(nums));
        System.out.println(canPartition2(nums));
    }
}
